學習資源

https://labuladong.online/algo/data-structure-basic/tree-map-basic/

學習記錄

今天是學習的第 27 天，主要學習了 TreeMap / TreeSet 實現原理：

TreeMap 和 HashMap 的差異

TreeMap 和哈希表 HashMap 的資料結構類似，都是儲存鍵值對 key-value，差別在於：

TreeMap / TreeSet 實現原理

這是一個基本的 TreeNode 結構：

var TreeNode = function(val) {
    this.val = val;
    this.left = null;
    this.right = null;
};

只需要調整這個 TreeNode 結構，就可以用來實現 TreeMap：

class TreeNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

TreeMap 結構

這是一個 TreeMap 的結構，雖然哈希表 HashMap 很實用，但是它沒有辦法很好的處理鍵之間的大小關係。

// TreeMap 主要接口
class MyTreeMap<K, V> {

    // ****** Map 鍵值映射的基本方法 ******

    // 增/改，複雜度 O(log n)
    public void put(K key, V value) {}

    // 查，複雜度 O(log n)
    public V get(K key) {}

    // 刪，複雜度 O(log n)
    public void remove(K key) {}

    // 是否包含鍵 key，複雜度 O(log n)
    public boolean containsKey(K key) {}

    // 返回所有鍵的集合，結果有序，複雜度 O(log n)
    public List<K> keys() {}

    // 查找小於等於 key 的最大鍵，複雜度 O(log n)
    public K floorKey(K key) {}

    // 查找大於等於 key 的最小鍵，複雜度 O(log n)
    public K ceilingKey(K key) {}

    // 查找排名為 k 的鍵，複雜度 O(log n)
    public K selectKey(int k) {}

    // 查找鍵 key 的排名，複雜度 O(log n)
    public int rank(K key) {}

    // 區間查找，複雜度 O(log n + m)，m 為區間大小
    public List<K> rangeKeys(K low, K high) {}
}

性能問題

核心原則：二叉搜索樹的性能取決於樹的高度，樹的高度取決於樹的平衡性

平衡樹 vs 不平衡樹

這是一棵平衡的二叉搜索樹：

這是一棵不平衡的二叉搜索樹，所有節點都只有右子樹，沒有左子樹：

學習總結

• TreeMap 的底層資料結構是二叉搜索樹
• 二叉搜索樹的性能取決於樹的高度，樹的高度取決於樹的平衡性